Local Area Networks (LANs) connect computing systems together. LANs of all types can be connected together using Media Access Control (MAC) bridges, as set forth in the “IEEE Standard for Information Technology, Telecommunications and Information Exchange between Systems, Local and Metropolitan Area Networks, Common Specifications, Part 3: Media Access Control (MAC) Bridges,” published as ANSI/IEEE Standard 802.1D (1998), which is incorporated herein by reference. The 802.1D standard is available at standards.ieee.org/catalog/IEEE802.1.html.
Each computing system connects to a LAN through a MAC device. MAC bridges that implement the 802.1D standard allows MAC devices attached to separate LANs to appear to each other as if they were attached to a single LAN. A MAC bridge functions within the Logical Link Control (LLC) sublayer of the Network Layer defined in ISO/IEC standard 7498-1: 1994, entitled “Information Processing Systems—Open Systems Interconnection-Basic Reference Model—Part 1: The Basic Model” (available from the American National Standards Institute, New York, N.Y.), which is incorporated herein by reference. The bridge includes two or more MAC devices that interconnect the bridge ports to respective LANs.
The discussion that follows is an abstract of the processes and services provided in a MAC bridge, in accordance with sections of IEEE 802.1D standard.
Section 6.6 of the 802.1D standard sets forth a filtering service in a bridged LAN. The filtering service provides for administrative control over the use of ports by a single MAC address or a group of addresses, and reduces the load placed on MAC devices caused by the reception of frames that are destined for other devices. It limits frames destined for specific MAC addresses to parts of the network which, to a high probability, lie along a path between the source MAC address and the destination MAC address. It also reduces the distribution of group-addressed frames to those parts of the network which contain MAC devices that are legitimate recipients of that traffic, thus increasing the overall throughput of the network.
The filtering service maintains a filtering database to determine whether to relay a specific frame from one port to another. Section 7.9, at page 42 of the 802.1D standard, defines static and dynamic entries in the database. Each entry maps a destination MAC address to a port of the bridge. While static entries are fixed, dynamic entries in the filtering database are updated though a learning process, set out in section 7.8, page 42 of the 802.1D standard. The learning process observes the source addresses of frames received on each port, and dynamically updates the filtering database (conditionally on the state of the receiving port). It either creates or updates an entry in the filtering database, associating the port on which the frame was received with the frame's source MAC address. If the filtering database is filled to capacity when a new entry is to be created, an existing entry is removed to make room for the new one.
An aging mechanism is set forth in section 7.9.2 of the 802.1D standard. The aging mechanism is responsible for deletion of dynamic entries in the filtering database, freeing space to new entries instead of old entries that have low chance of use and ensuring that MAC addresses that have moved to a different LAN will not be permanently prevented from receiving frames. It also allows changes of topology of a network that includes many bridges and LANs.
If a frame is received on a given port of a bridge with a destination MAC address that does not appear in the filtering database, the forwarding process of the bridge (section 7.7 of the 802.1D standard) performs a broadcast of the received frame, known as “flooding” the frame, through the other ports. The broadcast may be limited to a particular broadcast domain, i.e., to a group of stations in the network that can communicate as if they were on the same LAN. (Virtual LANs (VLANs), as described below, facilitate easy administration of such groups.) Even so, the frame broadcast performed by the forwarding process causes two problems: traffic load on the network, and computational load on the MAC bridge. Therefore, efficient management of the filtering database and of the learning process used to build the database are important, in order to minimize flooding.
The “IEEE Standard for Local and Metropolitan Area Networks: Virtual Bridged Local Area Networks,” published as IEEE Standard 802.1Q (1998), which is incorporated herein by reference, sets forth mechanisms for forming and managing VLANs. The 802.1Q standard is available at standards.ieee.org/catalog/IEEE802.1.html. Traffic between VLANs is restricted. Bridges in a VLAN environment forward unicast, multicast, and broadcast traffic only to ports that serve the VLAN to which the traffic belongs. MAC bridges in the VLAN environment must typically maintain their filtering databases as a shared resource among the different VLANs that they serve. The filtering database and the associated learning process must be modified accordingly. Entries in the database are identified both by their MAC address and their VLAN identifier. Optionally, information in the filtering database is shared among different VLANs using a Shared VLAN Learning (SVL) process defined in section 3.9 of the 802.1Q standard.
Multiprotocol Label Switching (MPLS) is gaining popularity as a method for efficient transportation of data packets over connectionless networks, such as Internet Protocol (IP) networks. MPLS is described in detail by Rosen et al., in Request for Comments (RFC) 3031 of the Internet Engineering Task Force (IETF), entitled “Multiprotocol Label Switching Architecture” (January, 2001), which is incorporated herein by reference. This RFC is available at www.ietf.org/rfc.html.
In conventional connectionless packet routing, each router along the path of a packet sent through the network analyzes the packet header and independently chooses the next hop for the packet by running a routing algorithm. In MPLS, however, each packet is assigned to a Forwarding Equivalence Class (FEC) when it enters the network, depending on its destination address. A short, fixed-length label identifying the FEC to which the packet belongs is pushed onto the top of a label stack, which is attached to the packet at the FEC ingress point. All packets in a given FEC are passed through the network over the same path by label-switching routers (LSRs). Unlike IP routers, LSRs simply use the packet label as an index to a look-up table, which specifies the next hop on the path for each FEC and the label that the LSR should attach to the packet for the next hop. The LSR pops the top label off the label stack, examines its destination address, and pushes another label onto the stack with the destination of the next hop.
The flow of packets along a label-switched path (LSP) under MPLS is completely specified by the label applied at the ingress of the path. A LSP is essentially a tunnel through the network, useful in network traffic management and communication security. MPLS tunnels are established by “binding” a particular label, assigned at the ingress node to the network, to a particular FEC.
Lasserre et al. describe a method to create a virtual LAN using a MPLS network in “Transparent VLAN services over MPLS” (July, 2001), which is incorporated herein by reference. This document is available at search.ietf.org/internet-drafts/draft-lasserre-tls-mpls-0 0.txt. A transparent LAN service (TLS) provides bridge-like functionality between multiple sites over a large network. Users connect to the TLS via regular node interfaces, and LSP(s) between the nodes to which the users are connected form the TLS entity itself. Every node in a TLS acts as a virtual bridge. A virtual bridge node has “virtual ports,” which are the endpoints of LSPs that are part of the TLS. The interfaces to which the users are actually connected are “real” ports. Both virtual and real interfaces are treated identically from the point of view of bridge processing (frame forwarding policies and loops prevention). A single LSP can participate in multiple TLS instances, each belonging to a different user.
The TLS network topology is completely specified by the LSP connections, which in turn depend on the MPLS protocol to actually transfer the packets through the virtual tunnels. Since MPLS networks supply an alternative, virtual implementation of layer 2 network communications, TLS can be thought of as parallel to conventional virtual bridged local area networks, as specified in the IEEE 802.1Q standard. From the perspective of the end user, the TLS network is transparent, and the user is provided with the illusion that the LSPs are single-hop connections between adjacent bridges.
Filtering databases are implemented in LSRs in much the same way as in MAC bridges. Each TLS is essentially a VLAN or a group of VLANs. The filtering database holds information allowing the LSR to determine, given a destination MAC address of a packet, the real or virtual port through which to transmit the packet. In contrast to most MAC bridges, however, LSRs are often implemented in software. Therefore, when flooding is necessary, it can impose a particularly heavy computational load on the LSR.
The filtering database is limited in size and is therefore vulnerable to malicious “denial-of-service” (DOS) attacks that attempt to explode the filtering database with irrelevant entries. An attack carried out on a particular MAC bridge can effectively destroy the filtering database for a large segment of the network. For example, a hacker may send streams of dummy packets to a MAC bridge or LSR, containing a sequence of bogus source addresses. The learning process of the bridge is forced to fill the database with useless relay information for these addresses. Eventually, valid information will be discarded from the database to make room for the useless information. When the bridge receives legal packets, its forwarding process must flood the packets through all its ports, since the destination addresses have been flushed from the database. As a result, the network is loaded with unnecessary traffic and may cease to function entirely.
In a VLAN or TLS environment, the filtering database maintained by each bridge must typically be shared among the VLANs or TLSs served by the bridge. It is generally not possible to hard-code the logic controlling the database in order to partition it into different VLAN or TLS domains. Therefore, an attack on the database in one of the domains may lead to denial of service in other domains, as well.